平成29年秋期 応用情報 午前 問6
ノード1〜5をもつグラフを隣接行列で表したもののうち，木となるものはどれか。ここで，隣接行列の$ i行$ j列目の成分は，ノード$ iとノード$ jを結ぶエッジがある場合は1，ない場合は0とする。 ア $ \begin{pmatrix} 0 & 1 & 0 & 0 & 1 \\\ 1 & 0 & 1 & 0 & 0 \\\ 0 & 1 & 0 & 1 & 0 \\\ 0 & 0 & 1 & 0 & 1 \\\ 1 & 0 & 0 & 1 & 0 \end{pmatrix}
イ $ \begin{pmatrix} 0 & 1 & 0 & 0 & 1 \\\ 1 & 0 & 1 & 1 & 0 \\\ 0 & 1 & 0 & 0 & 0 \\\ 0 & 1 & 0 & 0 & 0 \\\ 1 & 0 & 0 & 0 & 0 \end{pmatrix}
ウ $ \begin{pmatrix} 0 & 1 & 0 & 1 & 0 \\\ 1 & 0 & 1 & 0 & 0 \\\ 0 & 1 & 0 & 1 & 1 \\\ 1 & 0 & 1 & 0 & 0 \\\ 0 & 0 & 1 & 0 & 0 \end{pmatrix}
エ $ \begin{pmatrix} 0 & 1 & 1 & 0 & 0 \\\ 1 & 0 & 1 & 0 & 0 \\\ 1 & 1 & 0 & 1 & 1 \\\ 0 & 0 & 1 & 0 & 1 \\\ 0 & 0 & 1 & 1 & 0 \end{pmatrix}